package com.power.algorithm.sort;

/**
 * @description:
 * @author: jiangnan
 * @time: 2021/5/22 12:11 上午
 */
public class InsertionSort {
    static int[] array5 = Tools.createOrigin5Array();
    static int[] array100 = Tools.createOrigin100Array();
    static int[] testArray = Tools.testArray;
    static int[] testArray2 = Tools.testArray2;
    static int[] testArray3 = Tools.testArray3;


    public static void main(String[] args) {
        InsertionSort insertionSort = new InsertionSort();
        int[] arr = insertionSort.sort(testArray);
        Tools.display(arr);

         int[] arr2 = insertionSort.sort(array100);
         Tools.display(arr2);

        int[] arr3 = insertionSort.sort(testArray2);
        Tools.display(arr3);

        int[] arr4 = insertionSort.sort(testArray3);
        Tools.display(arr4);
    }

    /**
     * 1. 遍历整个数组
     * 2. 将遍历的元素插入已经排好序的数组中
     * 3. 移动元素
     */


    public int[] sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int pre = -1;
            for (int j = i; j > 0; j--) {
                //如果后面的元素比前面的元素小
                 pre = j-1;    //前一个元素
                //如果前一个元素大于后一个元素   则进行交换
                if (array[pre] > array[j]) {
                    int tmp = array[pre];
                    array[pre] = array[j];
                    array[j] = tmp;
                } else {
                    break;
                }

            }
        }


        return array;
    }
}
